package club.xiaojiawei.array;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/19 21:13
 * @question 977.有序数组的平方
 * @description 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 */
public class OrderlyArrSquare977 {

    public static void main(String[] args) {
        int[] arr = {-11, -9, -9, -5, -1, };
        System.out.println(Arrays.toString(sortedSquares1(arr)));
    }

    public static int[] sortedSquares(int[] nums) {
        Stack<Integer> temp = new Stack<>();
        int[] ints = new int[nums.length];
        int index = 0;
        int square;
        int i = 0;
        while (i < nums.length) {
            if (nums[i] < 0){
                temp.push(nums[i] * nums[i++]);
            }else if (temp.isEmpty()){
                ints[index++] = nums[i] * nums[i++];
            }else {
                if ((square = nums[i] * nums[i]) > temp.peek()){
                    ints[index++] = temp.pop();
                }else {
                    i++;
                    ints[index++] = square;
                }
            }
        }
        while (!temp.isEmpty()){
            ints[index++] = temp.pop();
        }
        return ints;
    }

    /**
     * 双指针，归并排序思想
     * @param nums
     * @return
     */
    public static int[] sortedSquares1(int[] nums) {
        int r = nums.length;
//        寻找正负数的分界点
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0){
                r = i;
                break;
            }
        }
        int l = r - 1;
        int[] ints =new int[nums.length];
        int index = 0;
//        归并排序的思想
        while (l > -1 && r < nums.length){
            if (-nums[l] < nums[r]){
                ints[index++] = nums[l] * nums[l--];
            }else {
                ints[index++] = nums[r] * nums[r++];
            }
        }
        while (l > -1){
            ints[index++] = nums[l] * nums[l--];
        }
        while (r < nums.length){
            ints[index++] = nums[r] * nums[r++];
        }
        return ints;
    }
}
